/**	动态内存堆---以运算时间换取空间的方式避免内存碎片
 * 
 * 管理表内存空间-->----------------
 * -------------------------------
 * -------------------------------
 * -------------------------------
 * ------------------<--数据内存空间
**/
#include "mem_malloc.h"

typedef struct mem_block{ 
    void			*mem_ptr;       //申请到的内存的起始地址
    unsigned int	mem_size;       //申请到的内存的大小，按照块大小分配，大于等于申请大小
    unsigned int	mem_index;      //申请表序号，申请内存时分配，获取内存起始地址与释放内存时使用
}mem_block;

#define BLK_SIZE	sizeof(mem_block)

/** 打印内存堆信息
 * const mem_heap* heap 内存堆对象
 * 无返回值
 **/
void print_heap_info(const mem_heap* heap){
	printf("------------mem_info--------------\n");
	printf("sizeof(mem_block)=%d\n", BLK_SIZE);
	printf("mem_start = %d(0x%x)\n", (int)(&(heap->mem[0])), (int)(&(heap->mem[0])));
	printf("MEM_END   = %d(0x%x)\n", (int)(&(heap->mem[heap->size])), (int)(&(heap->mem[heap->size])));	
	printf("MEM_SIZE  = %d(0x%x)\n", (int)(heap->size), (int)(heap->size));
	printf("----------------------------------\n");	
}

void print_hex(char *data, int len){
	for(int i=0; i<len; i++){
		printf("%02x ", (unsigned char)data[i]);
		if((i+1)%12 == 0)   printf("\n");
	}
	printf("\n");
}
/**	打印整个堆内存空间
 * const mem_heap* heap 堆空间对象
**/
void print_heap_hex(const mem_heap* heap){
	print_hex(heap->mem, heap->size);
}

/** 申请堆内存空间大小
 * const mem_heap* heap ： 内存堆的对象
 * unsigned int msize ：申请的大小
**/
int heap_malloc(mem_heap* heap,unsigned int msize){
	//1、计算分配总内存大小=申请内存大小+管理的表内存
	unsigned int all_size = msize + sizeof(mem_block);
	mem_block tmp_blk;
	if(msize == 0) return 0;
	if(heap->sum){ //非第一次分配
		//获取堆管理表空间的最后一份管理表
		mem_block *ptr_blk = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*((heap->sum)-1));
		//计算剩余空闲空间大小=堆数据空间的起始地址-堆管理表空间的结束地址
		int free_blk = (unsigned char *)ptr_blk->mem_ptr-(&(heap->mem[0]) + BLK_SIZE*(heap->sum));
		//需要分配的总内存小于空闲内存
		if(all_size <= free_blk){
			tmp_blk.mem_ptr = ptr_blk->mem_ptr - msize;
			tmp_blk.mem_size = msize;
			tmp_blk.mem_index = ptr_blk->mem_index + 1;
			memcpy(&(heap->mem[0])  + BLK_SIZE*(heap->sum), &tmp_blk, BLK_SIZE);
			heap->sum = (heap->sum) + 1;
		#if DEBUG_EN
			printf("mem_ptr = 0x%x\n", (int)tmp_blk.mem_ptr);
			printf("mem_size = 0x%x\n", tmp_blk.mem_size);
			printf("mem_index = 0x%x\n", tmp_blk.mem_index);
		#endif
			return tmp_blk.mem_index;
		}
	}else{	//第一次分配
		if(all_size <= (heap->size)){
			//申请的内存分配从内存堆尾部往头部分配
			tmp_blk.mem_ptr = &(heap->mem[heap->size]) - msize;
			tmp_blk.mem_size = msize;
			tmp_blk.mem_index = 1; 
			//分配的管理表的内存从堆的头部往尾部分配
			memcpy(&(heap->mem[0]), &tmp_blk, BLK_SIZE);
			heap->sum  = 1;
        #if DEBUG_EN
			printf("mem_ptr = 0x%x\n", (int)tmp_blk.mem_ptr);
			printf("mem_size = 0x%x\n", tmp_blk.mem_size);
			printf("mem_index = 0x%x\n", tmp_blk.mem_index);
        #endif
			return 1;
		}
	}
	return 0;
}

/**重新分配内存
 * mem_heap* heap ：内存堆对象
 * int id：表序号
 * unsigned int msize：重新分配的内存大小
 * 返回：1--重分配成功；0--重分配失败
**/
int heap_realloc(mem_heap* heap,int id, unsigned int msize){
	//1、遍历搜索出需要重新分配的表序号
	for(int i=0; i<(heap->sum); i++){
		mem_block *ptr_blk = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*i);
		if(id == ptr_blk->mem_index){
			int free_blk = (unsigned char *)ptr_blk->mem_ptr-(&(heap->mem[0]) + BLK_SIZE*(heap->sum));
			int old_size = ptr_blk->mem_size;
			int offset = msize - old_size;
			int move_size = 0; 
			int n = (heap->sum) - i;
			mem_block *ptr_tmp;
			if(offset == 0){
				return 0;
			}else if(offset < 0){
				offset = old_size - msize;
				for(int j=1; j<n; j++){
					ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
					move_size += ptr_tmp->mem_size;
				}
				if(n == 1){
					ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*i);
				}
				move_size += msize;
				char *dst_addr = (char*)ptr_tmp->mem_ptr + move_size + offset - 1;
				char *src_addr = (char*)ptr_tmp->mem_ptr + move_size - 1;
				for(int j=move_size; j>0; j--){
					*dst_addr-- = *src_addr--;
				}
				memset(src_addr, 0, offset+1);
				for(int j=0; j<n; j++){
					ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
					ptr_tmp->mem_ptr += offset;
					if(j == 0){
						ptr_tmp->mem_size = msize;
					}
				}
				return 1;
			}else{
				if(offset <= free_blk){
					for(int j=1; j<n; j++){
						ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
						move_size += ptr_tmp->mem_size;
					}
					if(n == 1){
						ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*i);
					}
					move_size += old_size;
					char *dst_addr = ptr_tmp->mem_ptr - offset;
					char *src_addr = ptr_tmp->mem_ptr;
					for(int j=0; j<move_size; j++){
						*dst_addr++ = *src_addr++;
					}
					for(int j=0; j<n; j++){
						ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
						ptr_tmp->mem_ptr -= offset;
						if(j == 0){
							ptr_tmp->mem_size = msize;
						}
					}
					return 1;				
				}
			}
		}
	}
	return 0;
}



/** 获取表序号的内存块起始地址
 * const mem_heap* heap :内存堆对象
 * int id ：申请表序号
 * 返回：指定表序号的内存块起始地址
 **/
void *heap_buffer(const mem_heap* heap,int id){
	for(int i=0; i<(heap->sum); i++){
		mem_block *ptr_blk = (mem_block *)(&(heap->mem[0])+ BLK_SIZE*i);
		if(id == ptr_blk->mem_index){
			return ptr_blk->mem_ptr;
		}
	}
	return NULL;
}

/** 内存资源释放函数
 * mem_heap* heap ：内存堆对象
 * int id ：内存资源的ID 
 **/
int heap_free(mem_heap* heap,int id){
	for(int i=0; i<(heap->sum); i++){
		mem_block *ptr_blk = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*i);
		if(id == ptr_blk->mem_index){
			mem_block *ptr_old;
			if(i != (heap->sum-1)){
				int offset = ptr_blk->mem_size;
				int move_size = 0; 
				int n = heap->sum - i;
				mem_block *ptr_tmp;
				for(int j=1; j<n; j++){
					ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
					move_size += ptr_tmp->mem_size;
				}
				//memmove();
				char *dst_addr = ptr_tmp->mem_ptr + move_size + offset - 1;
				char *src_addr = ptr_tmp->mem_ptr + move_size - 1;
				for(int j=move_size; j>0; j--){
					*dst_addr-- = *src_addr--;
				}
				memset(src_addr, 0, offset+1);
				for(int j=0; j<(n-1); j++){
					ptr_tmp = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j));
					ptr_old = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*(i+j+1));
					memcpy(ptr_tmp, ptr_old, BLK_SIZE);
					ptr_tmp->mem_ptr += offset;
				}
			}else{
				ptr_old = (mem_block *)(&(heap->mem[0]) + BLK_SIZE*i);
				memset(ptr_old->mem_ptr, 0, ptr_old->mem_size);
			}
			memset(ptr_old, 0, BLK_SIZE);
			heap->sum = heap->sum - 1;
			return 1;
		}
	}
	return 0;
}

